package com.leetcodehot.problems;

public class problems2698 {
    private int res = 0;
    private int temp = 0;
    private String str;

    public int punishmentNumber(int n) {
        for (int i = 1; i <= n; i++) {
            temp = 0;
            str = String.valueOf(i * i);
            if (isOk(i, 0, 0)) {
                res += i * i;
            }
        }
        return res;
    }

    //target*target拆分开 最终相加 等于target
    private boolean isOk(int target, int start, int end) {
        if (end == str.length()) {
            if (target == temp) {
                return true;
            }
            return false;
        }
        //选择当前
        temp += Integer.parseInt(str.substring(start, end + 1).trim());
        if (isOk(target, end + 1, end + 1)) {
            return true;
        }
        temp -= Integer.parseInt(str.substring(start, end + 1).trim());

        //不选
        if (end + 1 != str.length()) {
            return (isOk(target, start, end + 1));
        }

        temp += Integer.parseInt(str.substring(start, end + 1).trim());
        if (isOk(target, start, end + 1)) {
            return true;
        }
        temp -= Integer.parseInt(str.substring(start, end + 1).trim());
        return false;
    }
}
